package leetcode.f1t100;

/**
 * A-Z映射1-26,给一串数字字符串, 解码出对应的字符串可能有多少种
 * https://leetcode.com/problems/decode-ways/description/
 *
 * @author lichx
 * @createTime 2024/2/5 14:12
 */
public class Q91_DecodeWays {

    public static void main(String[] args) {
        Q91_DecodeWays bean = new Q91_DecodeWays();
        System.out.println(bean.numDecodings("1"));
        System.out.println(bean.numDecodings("11"));
        System.out.println(bean.numDecodings("111"));
        System.out.println(bean.numDecodings("1111"));
//        System.out.println(bean.numDecodings("111111111111111111111111111111111111111111111"));
//        System.out.println(bean.numDecodings("10"));
    }

    public int numDecodings(String s) {
        char[] chars = s.toCharArray();
//        return numDecodings(chars, 0);
//        return numDecodingsCache(chars, 0,  new int[chars.length+2]);
        return numDecodingsDp(chars);
    }


    private int numDecodingsDp(char[] chars) {
        if(chars[0] == '0'){
            return 0;
        }
        int dp[] = new int[chars.length+2];
        dp[chars.length] = 1;
        dp[chars.length+1] = 0;

        for (int left = chars.length -1 ; left >=0 ; left--) {

            if(chars[left] == '0') {
                dp[left] = 0;
                continue;
            }

            if(chars[left] == '1') {
                    if (left < chars.length - 1 && chars[left + 1] == '0') {
                        dp[left] = dp [left + 2];
                        continue;
                    }
                    dp[left] = dp[ left + 1] + dp[left + 2];
                    continue;
            }


            if (chars[left] == '2') {
                if (left < chars.length - 1 && (chars[left + 1] == '0' || chars[left + 1] > '6')) {
                    dp[left] = dp[ left + 2];
                    continue;
                }
                dp[left] = dp[left + 1] + dp[ left + 2];
                continue;
            }

            if (left < chars.length - 1 && chars[left + 1] == '0') {
                dp[left] = 0;
                continue;
            }
            dp[left] = dp[ left + 1];
        }
        return dp[0];
    }

    private int numDecodingsCache(char[] chars, int left, int[] cache) {
        if(cache[left] != 0) {
            return cache[left];
        }
        if (left == chars.length) {
            cache[left] = 1;
            return cache[left];
        }
        if(left > chars.length || chars[left] == '0') {
            cache[left] = 0;
            return cache[left];
        }

        if (chars[left] == '1') {
            if (left < chars.length - 1 && chars[left + 1] == '0') {
                cache[left] = numDecodings(chars, left + 2);
                return cache[left];
            }
            cache[left] = numDecodings(chars, left + 1) + numDecodings(chars, left + 2);
            return cache[left];
        }
        if (chars[left] == '2') {
            if (left < chars.length - 1 && (chars[left + 1] == '0' || chars[left + 1] > '6')) {
                cache[left] = numDecodings(chars, left + 2);
                return cache[left];
            }
            cache[left] = numDecodings(chars, left + 1) + numDecodings(chars, left + 2);
            return cache[left];
        }

        if (left < chars.length - 1 && chars[left + 1] == '0') {
            cache[left] = 0;
            return cache[left];
        }
        cache[left] = numDecodings(chars, left + 1);
        return cache[left];

    }

    private int numDecodings(char[] chars, int left) {
        if (left == chars.length) {
            return 1;
        }
        if(left > chars.length || chars[left] == '0') {
            return 0;
        }

        if (chars[left] == '1') {
            if (left < chars.length - 1 && chars[left + 1] == '0') {
                return numDecodings(chars, left + 2);
            }
            return numDecodings(chars, left + 1) + numDecodings(chars, left + 2);
        }
        if (chars[left] == '2') {
            if (left < chars.length - 1 && (chars[left + 1] == '0' || chars[left + 1] > '6')) {
                return numDecodings(chars, left + 2);
            }
            return numDecodings(chars, left + 1) + numDecodings(chars, left + 2);
        }

        if (left < chars.length - 1 && chars[left + 1] == '0') {
            return 0;
        }
        return numDecodings(chars, left + 1);

    }
}
